public class ILN{   // Infinitely Long Number
  protected boolean sign;
  protected int exp;
  protected String num;

  public static final ILN Zero = new ILN(true, 0, "0");

  // FOUR METHODS ##############

  public ILN minus(ILN oth){
    // make oth and self positive, ensure this.exp >= oth.exp
    if (!oth.sign) return plus(oth.to_neg());
    if (!sign)     return to_neg().plus(oth).to_neg();
    switch (cmp(oth)){
      case 1: return oth.minus(this).to_neg();
      case 0: return Zero;
    }

    String fnum = num;
    String bnum = oth.num;
    int fexp = exp;
    int bexp = oth.exp;

    // Adjust numbers so they line up 1:1
    while (fexp > bexp) {
      bnum = "0" + bnum;
      bexp ++;
    }
    while (fnum.length() < bnum.length()) fnum += "0";
    while (bnum.length() < fnum.length()) bnum += "0";

    // Subtracting loop
    char[] rnumc = new char[fnum.length()];
    int rexp = fexp;
    int carry = 0;
    for (int i = fnum.length() - 1; i >= 0; i--){
      int res = Character.digit(fnum.charAt(i), 10) -
        Character.digit(bnum.charAt(i), 10) - carry;
      if (res < 0){
        carry = 1;
        res += 10;
      }
      else{
        carry = 0;
      }
      rnumc[i] = Character.forDigit(res, 10);
    }

    String rnum = new String(rnumc);

    return new ILN(true, rexp, rnum);
  }

  public ILN over(ILN oth, int divideUntil){
    boolean rsign = !(sign ^ oth.sign);

    if (num.equals(oth.num)) return new ILN(rsign, exp - oth.exp, "1");
    if (oth.num.equals("1")) return new ILN(rsign, exp - oth.exp, num);

    ILN dividend = new ILN(true, 0, num);
    ILN divisor  = new ILN(true, 0, oth.num);
    ILN res = Zero;

    for (int i = 0;; i++){
      ILN divisori = divisor.shift(-i).abs();
      for (int j = 0; j < 10; j++){
        if (dividend.cmp(divisori) > 0) break;
        dividend = dividend.minus(divisori);
        res = res.plus(new ILN(true, exp - i, "1"));
        if (dividend.num.equals("0")) break;
      }
      // this may be sped up by solely comparing string "0"
      if (dividend.equals(Zero)) break;
      if (res.num.length() - divideUntil >= num.length()) break;
    }

    return new ILN(rsign, res.exp - oth.exp, res.num);
  }

  public ILN plus(ILN oth){
    // make oth and self positive, ensure this.exp >= oth.exp
    if (!oth.sign) return minus(oth.to_neg());
    if (!sign)     return oth.minus(to_neg());
    if (oth.exp > exp) return oth.plus(this);

    String fnum = num;
    String bnum = oth.num;
    int fexp = exp;
    int bexp = oth.exp;

    // Adjust numbers so they line up 1:1
    while (fexp > bexp) {
      bnum = "0" + bnum;
      bexp ++;
    }
    while (fnum.length() < bnum.length()) fnum += "0";
    while (bnum.length() < fnum.length()) bnum += "0";

    // Adding loop
    char[] rnumc = new char[fnum.length()];
    int rexp = fexp;
    int carry = 0;
    for (int i = fnum.length() - 1; i >= 0; i--){
      int res = carry + Character.digit(fnum.charAt(i), 10) +
        Character.digit(bnum.charAt(i), 10);
      if (res > 9){
        carry = 1;
        res %= 10;
      }
      else{
        carry = 0;
      }
      rnumc[i] = Character.forDigit(res, 10);
    }

    String rnum = new String(rnumc);
    
    if (carry == 1){
      rnum = "1" + rnum;
      rexp ++;
    }

    return new ILN(true, rexp, rnum);
  }

  public ILN times(ILN oth){
    if (num.length() > oth.num.length()) return oth.times(this);
    boolean rsign = !(sign ^ oth.sign);

    ILN rnum = Zero;
    ILN incby;
    for (int i = 0; i < num.length(); i++){
      incby = oth.abs().shift(exp - i);
      for (int j = 0; j < Character.digit(num.charAt(i), 10); j++)
        rnum = rnum.plus(incby);
    }

    rnum.sign = rsign;

    return rnum;
  }

  // HELPER METHODS ############

  public ILN abs(){
    return new ILN(true, exp, num);
  }

  public int cmp(ILN oth){
    if (sign && !oth.sign)  return -1;
    if (!sign && oth.sign)  return  1;
    if (!sign && !oth.sign) return -1 * to_neg().cmp(oth.to_neg());

    if (oth.exp > exp) return  1;
    if (exp > oth.exp) return -1;

    for (int i = 0;; i++){
      if (i == num.length() && i == oth.num.length()) return 0;
      if (i == num.length())     return  1;
      if (i == oth.num.length()) return -1;
      int fchr = Character.digit(num.charAt(i),     10);
      int bchr = Character.digit(oth.num.charAt(i), 10);
      if (fchr > bchr) return -1;
      if (bchr > fchr) return  1;
    }
  }

  public boolean equals(Object o){
    if (o.getClass() != getClass()) return false;

    ILN oth = (ILN)o;
    if (sign == oth.sign && num.equals(oth.num) && exp == oth.exp)
      return true;
    return false;
  }

  public ILN shift(int by){
    return new ILN(sign, exp + by, num);
  }

  public ILN to_neg(){
    return new ILN(!sign, exp, num);
  }

  public ILN ipart(){
    if (exp >= 0){
      if (exp + 1 <= num.length())
        return neu(toString().substring(0, exp + 3) + "e" + exp);
      else
        return neu(toString());
    }
    return neu("0");
  }

  public int toInt(){
    ILN intp = ipart();
    if (intp.equals(Zero)) return 0;
    String res = intp.num;
    for (int i = intp.num.length(); i < intp.exp + 1; i++){
      res += "0";
    }
    res = (intp.sign?"":"-") + res;
    return Integer.parseInt(res);
  }

  public String toString(){
    String nnum = "" + num.charAt(0) + ".";
    if (num.length() > 1) nnum += num.substring(1);
    return (sign? "+" : "-") + nnum + "e" + exp;
  }

  public String toString(int base, int divideUntil){
    String res = "";

    ILN num   = ipart();
    ILN lnum  = num;
    ILN ibase = neu("" + base);

    for (int remainder;;){
      if (num.equals(Zero)) break;
      num = num.over(ibase, divideUntil).ipart();
      remainder = Integer.parseInt(lnum.minus(num.times(ibase)).num);
      res = "" + Character.forDigit(remainder, base) + res;
      lnum = num;
    }

    res = (sign? "" : "-") + res;

    switch (base){
      case 2:
        res = "0b" + res;
        break;
      case 8:
        res = "0" + res;
        break;
      case 16:
        res = "0x" + res;
        break;
    }

    return res;
  }

  // CONSTRUCTOR ###############

  public ILN(boolean si, int ex, String nu){
    sign = si;
    exp  = ex;
    num  = nu;

    // eliminate leading zeroes
    while (num.charAt(0) == '0' && num.length() > 1){
      num = num.substring(1);
      exp --;
    }
    // eliminate trailing zeroes
    while (num.charAt(num.length() - 1) == '0' && num.length() > 1)
      num = num.substring(0, num.length() - 1);
  }

  public static ILN neu(String wha, int base){
    boolean sign;

    wha = wha.trim();

    if (wha.charAt(0) == '+'){
      sign = true;
      wha = wha.substring(1);
    }
    else if (wha.charAt(0) == '-'){
      sign = false;
      wha = wha.substring(1);
    }
    else sign = true;

    ILN curmult = neu("1");
    ILN ilnbase = neu("" + base);
    ILN res     = neu("0");

    for (int i = wha.length() - 1; i >= 0; i--){
      for (int j = Character.digit(wha.charAt(i), base); j > 0 ; j--)
        res = res.plus(curmult);
      curmult = curmult.times(ilnbase);
    }

    res.sign = sign;

    return res;
  }

  public static ILN neu(String wha){
    if (!wha.matches("[\\+\\-]?\\d+(\\.\\d*)?(e\\-?\\d+)?"))
      throw new RuntimeException("Sorry that string won't do (" +
          "\"" + wha + "\")");
    boolean si;
    String nu = wha;

    if (Character.isDigit(nu.charAt(0))) si = true;
    else{
      si = nu.charAt(0) == '+';
      nu = nu.substring(1);
    }

    int ex = 0;
    boolean exset = false;
    String res = "";
    for (int i = 0;; i++){
      if (i >= nu.length()) break;
      char c = nu.charAt(i);
      if (c == 'e'){
        nu = nu.substring(i);
        break;
      }
      if (c == '.'){
        ex = res.length() - 1;
        exset = true;
        continue;
      }
      res += c;
    }
    if (!exset){
      ex = res.length() - 1;
    }

    if (nu.charAt(0) == 'e') ex += Integer.parseInt(nu.substring(1));

    return new ILN(si, ex, res);
  }
}
